package linkedlist.test430;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/15 12:39
 */
public class Solution1 {

    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    // DFS深度优先遍历，先走child节点，然后走next节点(牛逼解法)
    Node prev = null;

    public Node flatten(Node head) {
        dfs(head);
        return head;
    }

    private void dfs(Node head) {
        if (head == null) return;
        Node next = head.next;
        if (prev != null) {
            prev.next = head;
            head.prev = prev;
        }
        prev = head;
        dfs(head.child);
        head.child = null;
        dfs(next);
    }
}
